package string

// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnr003/
// 查找字符串是否存在
// 算法: 直接遍历
// 时间复杂度: O(nm)
// 更优算法: KMP
func strStr(haystack string, needle string) int {
	if len(haystack) < len(needle) {
		return -1
	}
	if needle == "" {
		return 0
	}
	for index := 0; index < len(haystack); index++ {
		if haystack[index] == needle[0] {
			left, right := index, 0
			isMatch := true
			for left < len(haystack) && right < len(needle) {
				if haystack[left] != needle[right] {
					isMatch = false
					break
				}
				left++
				right++
			}
			if isMatch {
				return index
			}
		}
	}
	return -1
}
